The invention relates to a method and apparatus for generating halftone reproductions, and in particular to a method and apparatus generating at high-speed digital angled halftone screens reducing Moire effects in multicolour halftone reproduction.
As is known by people skilled in the art, digital halftoning refers to a process which:
a) takes as input a multivalued pixmap image; PA1 b) generates a multivalued dither threshold array having the desired screen angle, screen element period, and dot shape growth behavior determined by its threshold values; PA1 c) scans an output image pixmap covering the surface of the input image pixmap and for each output pixel, finds its corresponding locations both in the multivalued dither array and in the input pixmap image, compares corresponding input image pixel intensity values to dither array threshold values and accordingly writes pixels of one of two possible ouput intensity levels, for example white (on) or black (off) to the output image pixmap.
The multivalued dither array generally contains the discretization of a repetitive screening function. In order to limit the required memory size, the dither array contains only one or a few periods of the basic screen elements. Such a dither array is configured so as to tile the plane.
Traditional photographic halftoning for Cyan, Magenta, Yellow colour reproduction was based on three screens, all having an identical screening frequency and each one oriented 30.degree. away from each of the two other screen layers. In the case of 4 layers (Cyan, Magenta, Yellow, Black) the 3 darkest layers which are Cyan, Magenta and Black are arranged as mentioned above, and the fourth layer (Yellow) is placed at an angle of 15.degree. to one of the 3 main layers.
In the graphics industry, the most common method for reproducing halftone images using bilevel printing devices, is the ordered dither method. This method consists of subdividing the whole output image space into repetitive adjoining rectangular areas--screen elements. The inside of each screen element is gradually blackened according to the gray level of the original image, thus ensuring the presence of various gray levels in the reproduction. The method used to display or print color images can be reduced to the case of black/white images if the color image is considered to be separated into three independent color planes (red-green-blue or cyan-magenta-yellow) or into four independent color planes (cyan-magenta-yellow-black), each independent color plane being treated as a single halftone black/white image. However, as regards dither orientation and frequency, printing three or four separate color planes imposes very precise constraints; consequently, the parameters of the three or four separate color planes are dependent on one another. The dependence of dither orientations and frequencies is well known to those skilled in the art and is usually expressed in terms of angles and frequencies (periods) [HUN87].
Let us also emphasize that the relationships between the yellow plane and the three other color planes (cyan, black and magenta) are far less important than the relationships between the three cyan, black and magenta color planes. For this reason, the yellow plane is often not taken into account so as to concentrate on the problems created when superposing the three most important color planes (cyan, black and magenta).
According to the method used to produce the dither threshold values, it is possible to distinguish two main families of dithering methods: (a) dispersed-dot ordered dithering and (b) clustered-dot ordered dithering. The first of these two methods, dispersed-dot ordered dithering, has quite a strong artifact which appears as a visually disturbing horizontal and vertical structure. Moreover, the reproduction curve of this dither method is particularly non uniform. This explains why method (a) is rarely used for color reproduction. On the other hand, method (b), clustered-dot ordered dithering is known as the traditional dithering technique and requires approximating at high-precision exact irrational screen angles such as 15.degree., 30.degree., or 60.degree.. Clustered-dot ordered dithering is used in almost all high-resolution color reproduction devices as well as in many low and medium resolution devices. Despite being so common, clustered-dot ordered dither methods known in the art and applied at low and medium resolution (150-1200 dpi) produce (a) Moire effects due to poor approximations of the required screen angle and frequencies, (b) disturbing interference patterns due to the interference between the screen element period and the output pixmap grid period, (c) variations in the screen element period creating interference patterns due to unequal numbers of elementary cells in screen elements, (d) uneven behavior of intensity levels due to different sets of threshold dither values being associated with different screen elements.
The present disclosure is the first to present a method for minimizing Moire effects by applying discrete one-to-one rotation, producing colour separations where screen periods and angles are rendered very accurately, where the number of elementary cells per screen element is kept constant and where threshold values associated with each elementary screen element cell remain constant throughout the rotation process. The methods of this invention therefore provide colour separations having much less artifacts and interferences than previous methods known in the art. None of the methods of the art preserves in a rotated dither tile both the exact number of cells for each screen element and their exact dither threshold values, i.e. the shape growth behavior of the original non-rotated screen dot.
One method for computing an output halftone image was claimed in U.S. Pat. No. 4,350,996 (Rosenfeld). A screen function is generated, sampled and stored as an array of dither values tiling the halftone image plane. The sampling step is smaller than the output pixel step. Halftoning with rotated screens is obtained by applying inverse rotation to the current pixel output plane pointer in order to find its position in the dither plane. The method is accurate and fast, but since the "virtually" rotated dither grid represents the discretization of a screen function having an orientation and a period which differs from the output sampling grid, rotated grey ramps may show disturbing interference patterns at low resolution (200 to 1200 dpi).
The method claimed in European Patent Applications 0 427 380 A2 (Schiller), 0 498 106 A2 (Schiller), 0 499 738 A2 (Schiller, Knuth) try to avoid irregularities in grey ramps by producing correctly oriented dither tiles with screen elements each having an equal or close to equal number of elementary cells. The elementary cells within the screen element incorporate different sets of dither levels due to the varying phase relationship between the elementary cells and the dither threshold generating spot function. Interference patterns may be produced due to the interference between the screen element period and the output resolution sample period. Furthermore, the proposed methods are slow to produce dither tiles since they assign each pixel to one of the screen cells in the tile by a rather complex and slow equalization process.
The discrete one-to-one rotation method described in the present invention offers means unknown in the art for generating rotated screens which approximate irrational angles with high-precision producing much less disturbing interferences and artifacts than methods known in the art. Therefore, a carefully prepared dither tile incorporating screen elements with the desired period, initial orientation, and dither threshold values defining their screen dot shape growth behavior can be rotated by discrete one-to-one rotation and keep the desired screen element period, the number of cells per screen element and the threshold values associated with each screen element cell, thereby preserving the screen dot shape growth behavior of the original dither tile.
Since most of the disclosed one-to-one rotation techniques require only simple operations, such as additions, subtractions, shifts, replications and table accesses, rotated dither tiles may be generated much faster than by methods known in the previous art.
With discrete one-to-one rotation very high quality results at resolutions between 200 and 800 dpi are obtained for traditional screens having relative orientations of 0.degree., 30.degree., and 60.degree..